package leecode;

import java.util.Arrays;
/**
 * 题目：绝对值差值和
 * 给你两个正整数数组 nums1 和 nums2 ，数组的长度都是 n 。
 * 数组 nums1 和 nums2 的 绝对差值和 定义为所有 |nums1[i] - nums2[i]|（0 <= i < n）的 总和（下标从 0 开始）。
 * 你可以选用 nums1 中的 任意一个 元素来替换 nums1 中的 至多 一个元素，以 最小化 绝对差值和。
 * 在替换数组 nums1 中最多一个元素 之后 ，返回最小绝对差值和。因为答案可能很大，所以需要对 10e9 + 7 取余 后返回。
 *
 * |x| 定义为：
 * 如果 x >= 0 ，值为 x ，或者
 * 如果 x <= 0 ，值为 -x
 *
 */
class Solution_1818 {
    public static int minAbsoluteSumDiff(int[] nums1, int[] nums2) {
        final int MOD = 1000000007;
        int n = nums1.length;
        int[] rec = new int[n];
        // 数组复制，仅复制内容
        // System.arraycopy(nums1, 0, rec, 0, n);
        rec = nums1.clone();
        // Arrays的静态排序算法
        Arrays.sort(rec);
        int sum = 0;
        int maxn = 0;
        for (int i = 0; i < n; i++) {

            // 该二元组的绝对值差值
            int diff = Math.abs(nums1[i] - nums2[i]);

            // 绝对差值和
            sum = (sum + diff) % MOD;

            // 找到nums1中接近nums2[i]的两个元素下标，j-1和j
            // rec[j-1]<nums2[i]<=rec[j]
            int j = binarySearch(rec, nums2[i]);


            // j < n,说明nums2[i]离rec[j]更近
            if (j < n) {
                maxn = Math.max(maxn, diff - (rec[j] - nums2[i]));
            }

            // j > 0，说明nums2[i]离rec[j - 1]更近
            if (j > 0) {
                maxn = Math.max(maxn, diff - (nums2[i] - rec[j - 1]));
            }
        }
        return (sum - maxn + MOD) % MOD;
    }


    /**
     * 改良版二元搜索（针对有序数组），对于一个已知数组和一个给定目标值，返回离目标最近的元素下标
     * @param rec
     * @param target
     * @return 返回的下标有 rec[low-1]<target<=rec[low]
     */
    public static int binarySearch(int[] rec, int target) {
        int low = 0;
        int high = rec.length - 1;

        // 和最大元素进行比较，比最大元素还大的话，返回数组长度
        if (rec[high] < target ) {
            return high+1;
        }

        //结束条件为low==high
        while (low < high) {

            // 确定分界点，整型数据相除，自动取下整，将数组分成 low~mid 和 mid+1~high 两部分
            int mid = (high - low) / 2 + low;

            // 判断，与前半部分的最大值比较，缩小范围，直至掉入的范围只有一个元素，low==mid
            if (rec[mid] < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }

        return low;
    }


    public static void main(String[] args) {
        int[] nums1 = new int[]{1,10,4,4,2,7};
        int[] nums2 = new int[]{9,3,5,1,7,4};

        System.out.println(Solution_1818.minAbsoluteSumDiff(nums1,nums2));

    }
}
